//https://leetcode.cn/problems/smallest-number-in-infinite-set/description/?envType=daily-question&envId=2023-11-29




class SmallestInfiniteSet {
public:
    std::unordered_map<int, int> s;
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 使用std::greater<int>确保优先队列按照升序排列

    SmallestInfiniteSet() {
        for (int i = 1; i <= 1000; ++i) {
            s[i]++;
            pq.push(i);
        }
    }
    
    int popSmallest() {
        int res = pq.top();
        s[res]--;
        if (s[res] == 0) {
            s.erase(res); // 如果元素个数为0，则从映射中删除该元素
        }
        pq.pop();
        return res;
    }
    
    void addBack(int num) {
        if (s.find(num) == s.end()) { // 如果num不在集合中
            pq.push(num);
            s[num]++;
        }
    }
};


/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
 * int param_1 = obj->popSmallest();
 * obj->addBack(num);
 */